package searchmethods;

import agent.Problem;
import agent.Solution;
import agent.State;
import java.util.List;
import utils.NodeLinkedList;

public class DepthFirstSearch extends GraphSearch<NodeLinkedList> {

    public DepthFirstSearch() {
        frontier = new NodeLinkedList();
    }

    //Graph Search without explored list
    @Override
    protected Solution graphSearch(Problem problem){
//initialize the frontier using the initial state of problem
//initialize the explored set to be empty
        frontier.clear();
        frontier.add(new Node(problem.getInitialState()));
        
        while(!frontier.isEmpty() && !stopped){
            Node n;       // remove the first node from the frontier
            n = frontier.poll();
            
            if(problem.isGoal(n.getState())){
                return new Solution(problem, n);
            }
                        
            List<State> successors = problem.executeActions(n.getState());
            addSuccessorsToFrontier(successors, n);
            
            computeStatistics(successors.size());
        }
        return null;        // failure return
    
    }

    public void addSuccessorsToFrontier(List<State> successors, Node parent) {
         for(State state : successors){
            if(!frontier.containsState(state)){
                Node n = new Node(state, parent);
                
                if(!n.isCycle()){
                    frontier.addFirst(n);
                }
            }
        }
    }

    @Override
    public String toString() {
        return "Depth first search";
    }
}
